package com.sakura.二分查找;

public class Code704_二分查找 {

    public int search(int[] nums, int target) {
        int ans = lowerBound(nums, target);
        return ans < nums.length && nums[ans] == target ? ans : -1;
    }

    // lowerBound 返回最小的满足 nums[i] >= target 的 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.length
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]


    // 闭区间写法
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1; //范围缩小 [mid + 1, right]
            } else {
                right = mid - 1; // 范围缩小 [left, mid - 1]
            }
        }
        return left;
    }

    // 半开区间写法
    private int lowerBound2(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1; //范围缩小 [mid + 1, right)
            } else {
                right = mid; // 范围缩小 [left, mid)
            }
        }
        return left;
    }

    // 开区间写法
    private int lowerBound3(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid; //范围缩小 (mid, right)
            } else {
                right = mid; // 范围缩小 (left, mid)
            }
        }
        return right;
    }
}
